package com.wyh.domain.vo.groupOne.utils;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 深度优先搜索DFS进行模糊查询
 */
public class TreeSearch {

//    要进行深度优先搜索就调用这个方法，给出该树的根节点然后给出要搜索的字符串
    public static List<MasterDataTreeNode> searchTree(MasterDataTreeNode root, String searchString) {
        List<MasterDataTreeNode> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        if (containsAllCharactersInAnyOrder(root.getName(), searchString)) {
            result.add(copyTree(root)); // 将匹配节点及其子树添加到结果中
        } else {
            for (MasterDataTreeNode child : root.getChildren()) {
                result.addAll(searchTree(child, searchString));
            }
        }
        return result;
    }

    private static MasterDataTreeNode copyTree(MasterDataTreeNode node) {
        MasterDataTreeNode newNode = new MasterDataTreeNode(node.getUnique_id(), node.getId(), node.getName(), node.getType(), node.getState());
        for (MasterDataTreeNode child : node.getChildren()) {
            newNode.getChildren().add(copyTree(child));
        }
        return newNode;
    }



    public static List<Integer> findRoomAndParkingSpotIds(MasterDataTreeNode root, Integer uniqueId) {
        Map<Integer, MasterDataTreeNode> nodeMap = new HashMap<>();
        buildNodeMap(root, nodeMap);

        MasterDataTreeNode targetNode = nodeMap.get(uniqueId);
        if (targetNode == null) {
            return new ArrayList<>();
        }

        List<Integer> result = new ArrayList<>();
        dfs(targetNode, result);

        return result;
    }

    private static void dfs(MasterDataTreeNode node, List<Integer> result) {
        if (node == null) {
            return;
        }

        if ("room".equals(node.getType()) || "parkingSpot".equals(node.getType())) {
            result.add(node.getId());
        }

        for (MasterDataTreeNode child : node.getChildren()) {
            dfs(child, result);
        }
    }

    public static void buildNodeMap(MasterDataTreeNode node, Map<Integer, MasterDataTreeNode> nodeMap) {
        if (node == null) {
            return;
        }

        nodeMap.put(node.getUnique_id(), node);

        for (MasterDataTreeNode child : node.getChildren()) {
            buildNodeMap(child, nodeMap);
        }
    }

    public static boolean containsAllCharactersInAnyOrder(String name, String searchString) {
        // Convert the name to a frequency map
        Map<Character, Integer> nameFreq = new HashMap<>();
        for (char c : name.toCharArray()) {
            nameFreq.put(c, nameFreq.getOrDefault(c, 0) + 1);
        }

        // Check if all characters in searchString are in the frequency map
        for (char c : searchString.toCharArray()) {
            if (c == ' ') {
                continue; // Ignore spaces
            }
            if (!nameFreq.containsKey(c) || nameFreq.get(c) == 0) {
                return false;
            }
            nameFreq.put(c, nameFreq.get(c) - 1);
        }

        return true;
    }
}

